(display "\n========================================\n")
; 平均阻尼
(define (average-damp f)
    (lambda (x) (/ (+ x (f x)) 2)))

; 求不动点
(define (fix-point f guess)
    (define tolerance 0.00001)
    (define (close-enough? a b)
        (< (abs (- a b)) tolerance))
    (define (try guess)
        (let ((next (f guess)))
            (if (close-enough? next guess)
                next
                (try next))))
    (try guess))

; ; 测试 cos 的不动点
; (display (fix-point cos 1.0))
; (newline)

; ; 测试平方根
; (define (sqrt x)
;     (fix-point (average-damp (lambda (y) (/ x y)))
;                 1.0))
; (display (sqrt 2))
; (newline)

; ; 测试立方根
; (define (cube-root x)
;     (fix-point (average-damp (lambda (y) (/ x (* y y))))
;                 1.0))
; (display (cube-root 2))
; (newline)

; 测试 4 次方根
(define (fourth-root x)
    (fix-point (average-damp (average-damp (lambda (y) (/ x (* y y y)))))
                1.0))
(display (fourth-root 16))
(newline)

; 重复过程
(define (repeate f n)
    (define (compose f g)
        (lambda (x) (f (g x))))
    (define (iter i fi)
        (if (= i n)
            fi
            (iter (+ i 1)
                (compose f fi))))
    (iter 1 f))

; 基于重复过程的 4 次方根测试
(define (fourth-root x)
    (fix-point ((repeate average-damp 2) (lambda (y) (/ x (* y y y))))
                1.0))

(display (fourth-root 16))
(newline)

(define (nth-root x n)
    (define (lg n)
        (cond   ((> (/ n 2) 1) (+ 1 (lg (/ n 2))))
                ((< (/ n 2) 1) 0)
                (else 1)))
    (define (exp a n)
        (define (iter i result)
            (if (= i n)
                result
                (iter (+ i 1) (* a result))))
        (iter 0 1))
    (fix-point ((repeate average-damp (lg n)) (lambda (y) (/ x (exp y (- n 1)))))
                1.0))

(display (nth-root 100 100))
(newline)

; 2、3 次方根需要 1 次平均阻尼
; 4～7 次方根需要 2 次平均阻尼
; 8 次方根需要 3 次平均阻尼
; n 次方根需要 lgn 次平均阻尼

(display "\n========================================\n")
